import tool.ListNode;

/**
 * 反转一个单链表。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 * 进阶:
 * 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q00206s {
    public ListNode reverseList(ListNode head) {
        if (head == null) return head;
        ListNode hair = new ListNode(0);
        hair.next = head;
        // hair    head   next   nn
        // 0  ->  1  ->  2  ->  3  ->  4  ->  5  ->  NULL
        //       tail
        while (head.next != null) {
            ListNode next = head.next;
            ListNode tail = hair.next;
            head.next = head.next.next; // head指向nn
            hair.next = next; // op指向next
            next.next = tail; // next指向tail
        }
        return hair.next;
    }
}
